package hot100;

public class LowestCommonAncestor {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    private TreeNode commonAncestor = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        findLowestCommonAncestor(root,p,q);
        return commonAncestor;
    }

    private boolean[] findLowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return new boolean[]{false,false};

        if (root == p && root == q) {
            commonAncestor = root;
        }

        if (commonAncestor != null) return new boolean[]{true,true};

        boolean[] left = findLowestCommonAncestor(root.left, p, q);
        boolean[] right = findLowestCommonAncestor(root.right, p, q);

        boolean[] cur = new boolean[2];
        cur[0] |= root == p;
        cur[1] |= root == q;

        cur[0] |= (left[0] | right[0]);
        cur[1] |= (left[1] | right[1]);

        if (cur[0] && cur[1] && commonAncestor == null) {
            commonAncestor = root;
        }

        return cur;
    }
}
